#ifndef DEQUECORE_H_INCLUDED
#define DEQUECORE_H_INCLUDED

#include "Constants.h"
#include "MemoryManager.h"
#include <cstring>

namespace CEngine {

template<class T>
Deque<T>::Deque(void)
    :   array(),
        size(0),
        start(0),
        startArray(0),
        startIndice(0),
        startPointer(NULL),
        endArray(0),
        endIndice(0),
        endPointer(NULL)
{}

template<class T>
Deque<T>::Deque(const U64 numberOfElements)
    :   array(),
        size(numberOfElements),
        start(0),
        startArray(0),
        startIndice(0),
        startPointer(NULL),
        endArray((numberOfElements - 1) / Constants::Containers::dequeBlockSize),
        endIndice((numberOfElements - 1) % Constants::Containers::dequeBlockSize),
        endPointer(NULL)
{
    U64 blocksNeeded = numberOfElements / Constants::Containers::dequeBlockSize;
    if((numberOfElements % Constants::Containers::dequeBlockSize) != 0) {
        ++blocksNeeded;
    }

    U64 n = numberOfElements;
    for (U64 i = 0; i < blocksNeeded; ++i) {
        T* block = (T*)MemoryManager::rawAlloc(sizeof(T) * Constants::Containers::dequeBlockSize);
        array.pushBack(block);

        U64 temp;
        if(n > Constants::Containers::dequeBlockSize) {
            temp = Constants::Containers::dequeBlockSize;
            n -= Constants::Containers::dequeBlockSize;
        }
        else {
            temp = n;
            n -= Constants::Containers::dequeBlockSize;
        }
        for (U64 i = 0; i < temp; ++i) {
            block[i] = T();
        }
    }

    startPointer = &getElement(0);
    endPointer = &getElement(size - 1);
}

template<class T>
Deque<T>::Deque(const U64 numberOfElements, const T& element)
    :   array(),
        size(numberOfElements),
        start(0),
        startArray(0),
        startIndice(0),
        startPointer(NULL),
        endArray((numberOfElements - 1) / Constants::Containers::dequeBlockSize),
        endIndice((numberOfElements - 1) % Constants::Containers::dequeBlockSize),
        endPointer(NULL)
{
    U64 blocksNeeded = numberOfElements / Constants::Containers::dequeBlockSize;
    if((numberOfElements % Constants::Containers::dequeBlockSize) != 0) {
        ++blocksNeeded;
    }

    U64 n = numberOfElements;
    for (U64 i = 0; i < blocksNeeded; ++i) {
        T* block = (T*)MemoryManager::rawAlloc(sizeof(T) * Constants::Containers::dequeBlockSize);
        array.pushBack(block);

        U64 temp;
        if(n > Constants::Containers::dequeBlockSize) {
            temp = Constants::Containers::dequeBlockSize;
            n -= Constants::Containers::dequeBlockSize;
        }
        else {
            temp = n;
            n -= Constants::Containers::dequeBlockSize;
        }
        for (U64 i = 0; i < temp; ++i) {
            block[i] = element;
        }
    }

    startPointer = &getElement(0);
    endPointer = &getElement(size - 1);
}

template<class T>
Deque<T>::Deque(const Iterator<T>& first, const Iterator<T>& last)
    :   array(),
        start(0),
        startArray(0),
        startIndice(0),
        startPointer(NULL),
        endPointer(NULL)
{
    ASSERT(first < last);

    U64 numberOfElements = last.getPosition() - first.getPosition();
    size = numberOfElements;
    endArray = (numberOfElements - 1) / Constants::Containers::dequeBlockSize;
    endIndice = (numberOfElements - 1) % Constants::Containers::dequeBlockSize;

    U64 blocksNeeded = numberOfElements / Constants::Containers::dequeBlockSize;
    if((numberOfElements % Constants::Containers::dequeBlockSize) != 0) {
        ++blocksNeeded;
    }

    Iterator<T> it = first;
    for (U64 i = 0; i < blocksNeeded; ++i) {
        T* block = (T*)MemoryManager::rawAlloc(sizeof(T) * Constants::Containers::dequeBlockSize);
        array.pushBack(block);

        U64 temp;
        if(numberOfElements > Constants::Containers::dequeBlockSize) {
            temp = Constants::Containers::dequeBlockSize;
            numberOfElements -= Constants::Containers::dequeBlockSize;
        }
        else {
            temp = numberOfElements;
            numberOfElements -= Constants::Containers::dequeBlockSize;
        }
        for (; it != last; ++it) {
            block[i] = *it;
        }
    }

    startPointer = &getElement(0);
    endPointer = &getElement(size - 1);
}

template<class T>
Deque<T>::Deque(const Deque<T>& deque)
    :   array(),
        size(deque.size),
        start(deque.start),
        startArray(0),
        startIndice(0),
        startPointer(NULL),
        endArray(0),
        endIndice(0),
        endPointer(NULL)
{
    for (U64 i = 0; i < deque.array.getSize(); ++i) {
        T* block = (T*)MemoryManager::rawAlloc(sizeof(T) * Constants::Containers::dequeBlockSize);
        array.pushBack(block);

        if(i == 0) {
            memcpy(array[i] + start, deque.array.getRawArray(), Constants::Containers::dequeBlockSize - start);
        }
        else if(i == (array.getSize() - 1)) {
            memcpy(array[i], deque.array.getRawArray() + i, size % Constants::Containers::dequeBlockSize);
        }
        else {
            memcpy(array[i], deque.array.getRawArray() + i, Constants::Containers::dequeBlockSize);
        }
    }

    startArray = start / Constants::Containers::dequeBlockSize;
    startIndice = start % Constants::Containers::dequeBlockSize;
    startPointer = &getElement(0);

    endArray = (start + size - 1) / Constants::Containers::dequeBlockSize;
    endIndice = (start + size - 1) % Constants::Containers::dequeBlockSize;
    endPointer = &getElement(size - 1);
}

template<class T>
Deque<T>&
Deque<T>::operator=(const Deque<T>& deque) {
    if(this == &deque) {
        return *this;
    }

    for (U64 i = 0; i < size; ++i) {
        getElement(i).~T();
    }

    if(deque.array.getSize() > array.getSize()) {
        T* block = (T*)MemoryManager::rawAlloc(sizeof(T) * Constants::Containers::dequeBlockSize);
        array.pushBack(block);
    }

    size = deque.size;
    start = deque.start;

    I64 spacing = (array.getSize() - deque.array.getSize());
    if(spacing > 0) {
        spacing /= 2;
    }
    else {
        spacing = 0;
    }
    for (U64 i = 0; i < deque.array.getSize(); ++i) {
        if(i == 0) {
            memcpy(array[i + spacing] + start, deque.array.getRawArray(), Constants::Containers::dequeBlockSize - start);
        }
        else if(i == (array.getSize() - 1)) {
            memcpy(array[i + spacing], deque.array.getRawArray() + i, size % Constants::Containers::dequeBlockSize);
        }
        else {
            memcpy(array[i + spacing], deque.array.getRawArray() + i, Constants::Containers::dequeBlockSize);
        }
    }

    startArray = start / Constants::Containers::dequeBlockSize;
    startIndice = start % Constants::Containers::dequeBlockSize;
    startPointer = &getElement(0);

    endArray = (start + size - 1) / Constants::Containers::dequeBlockSize;
    endIndice = (start + size - 1) % Constants::Containers::dequeBlockSize;
    endPointer = &getElement(size - 1);
}

template<class T>
Deque<T>::~Deque(void) {
    for (U64 i = 0; i < size; ++i) {
        getElement(i).~T();
    }

    while(!array.isEmpty()) {
        MemoryManager::free(array.back());
        array.popBack();
    }

    startPointer = NULL;
    endPointer = NULL;
}

template<class T>
typename Deque<T>::DequeIterator Deque<T>::begin(void) const {
    DequeIterator it = {0};
    if(size == 0) {
        return it;
    }

    it.basePointer = const_cast<Deque<T>*>(this);
    it.currentArray = array.getRawArray() + startArray;
    it.startPointer = *it.currentArray;
    it.currentPointer = startPointer;
    it.endPointer = it.startPointer + Constants::Containers::dequeBlockSize;
    it.position = 0;

    return it;
}

template<class T>
typename Deque<T>::DequeIterator Deque<T>::rBegin(void) const {
    DequeIterator it = {0};
    if(size == 0) {
        return it;
    }

    it.basePointer = const_cast<Deque<T>*>(this);
    it.currentArray = array.getRawArray() + endArray;
    it.startPointer = *it.currentArray;
    it.currentPointer = endPointer;
    it.endPointer = it.startPointer + Constants::Containers::dequeBlockSize;
    it.position = size - 1;

    return it;
}

template<class T>
typename Deque<T>::DequeIterator Deque<T>::end(void) const {
    DequeIterator it = {0};
    if(size == 0) {
        return it;
    }

    it.basePointer = const_cast<Deque<T>*>(this);

    it.startPointer = *(array.getRawArray() + endArray);
    it.currentPointer = endPointer + 1;
    if(it.currentPointer == (it.startPointer + Constants::Containers::dequeBlockSize)) {
        it.currentArray = array.getRawArray() + endArray + 1;
        it.startPointer = *it.currentArray;
        it.currentPointer = it.startPointer;
        it.endPointer = it.startPointer + Constants::Containers::dequeBlockSize;
    }
    else {
        it.currentArray = array.getRawArray() + endArray;
        it.currentPointer = endPointer + 1;
        it.endPointer = *(array.getRawArray() + endArray) + Constants::Containers::dequeBlockSize;
    }
    it.position = size;

    return it;
}

template<class T>
typename Deque<T>::DequeIterator Deque<T>::rEnd(void) const {
    DequeIterator it = {0};
    if(size == 0) {
        return it;
    }

    it.basePointer = const_cast<Deque<T>*>(this);

    it.startPointer = *(array.getRawArray() + startArray);
    it.currentPointer = startPointer;
    if(it.currentPointer == *it.startPointer) {
        it.currentArray = startArray - 1;
        it.startPointer = *it.currentArray;
        it.currentPointer = it.startPointer + Constants::Containers::dequeBlockSize - 1;
        it.endPointer = it.startPointer + Constants::Containers::dequeBlockSize;
    }
    else {
        it.currentArray = startArray;
        it.currentPointer = startPointer - 1;
        it.endPointer = it.startPointer + Constants::Containers::dequeBlockSize;
    }
    it.position = (U64)(0 - 1);

    return it;
}

template<class T>
T& Deque<T>::front(void) {
    if(size == 0) {
        defaultLog.log(CEngine::Logging::CONTAINERS, LOG_ERROR, "Accessed element in empty container!\n");
    }

    return *startPointer;
}

template<class T>
T& Deque<T>::back(void) {
    if(size == 0) {
        defaultLog.log(CEngine::Logging::CONTAINERS, LOG_ERROR, "Accessed element in empty container!\n");
    }

    return *endPointer;
}

template<class T>
void Deque<T>::pushFront(const T& element) {
    bool blockAdded = false;
    if(start == 0) {
        T* block = (T*)MemoryManager::rawAlloc(sizeof(T) * Constants::Containers::dequeBlockSize);
        array.insert(0, block);
        start = Constants::Containers::dequeBlockSize;
        blockAdded = true;
    }

    --start;
    ++size;

    --startIndice;
    if(startIndice == (U64)(0 - 1)) {
        startIndice = Constants::Containers::dequeBlockSize - 1;
        if(blockAdded) {
            startPointer = &array.getRawArray()[startArray][startIndice];
        }
        else {
            startPointer = &array.getRawArray()[--startArray][startIndice];
        }
    }

    *startPointer = element;

    if(size == 1) {
        endPointer = startPointer;
        endArray = startArray;
        endIndice = startIndice;
    }
}

template<class T>
void Deque<T>::popFront(void) {
    if(size == 0) {
        return;
    }

    startPointer->~T();
    ++start;
    --size;

    ++startIndice;
    if(startIndice == Constants::Containers::dequeBlockSize) {
        startIndice = 0;
        startPointer = &array.getRawArray()[++startArray][startIndice];
    }
    else {
        ++startPointer;
        ++startIndice;
    }
}

template<class T>
void Deque<T>::pushBack(const T& element) {
    if((start + size) == (array.getSize() * Constants::Containers::dequeBlockSize)) {
        T* block = (T*)MemoryManager::rawAlloc(sizeof(T) * Constants::Containers::dequeBlockSize);
        array.pushBack(block);
    }

    ++size;

    if(size == 1) {
        endPointer = *array.getRawArray();
        startPointer = endPointer;
        startArray = endArray;
        startIndice = endIndice;
    }
    else {
        ++endIndice;
        if(endIndice == Constants::Containers::dequeBlockSize) {
            endIndice = 0;
            endPointer = &array.getRawArray()[++endArray][endIndice];
        }
        else {
            ++endPointer;
        }
    }

    *endPointer = element;
}

template<class T>
void Deque<T>::popBack(void) {
    if(size == 0) {
        return;
    }

    endPointer->~T();

    --endIndice;
    if(endIndice == (U64)(0 - 1)) {
        endIndice = Constants::Containers::dequeBlockSize - 1;
        endPointer = &array.getRawArray()[--endArray][endIndice];
    }
    else {
        --endPointer;
        --endIndice;
    }

    --size;
}

template<class T>
void Deque<T>::clear(void) {
    for (U64 i = 0; i < size; ++i) {
        getElement(i).~T();
    }

    size = 0;
    start = (array.getSize() / 3) * Constants::Containers::dequeBlockSize;
    startArray = array.getSize() / 3;
    startIndice = 0;
    startPointer = NULL;
    endArray = startArray;
    endIndice = startIndice;
    endPointer = NULL;

}

template<class T>
bool Deque<T>::isEmpty(void) const {
    if(size == 0) {
        return true;
    }
    return false;
}

template<class T>
U64 Deque<T>::getSize(void) const {
    return size;
}

template<class T>
T& Deque<T>::getElement(const U64 position) {
    return array.getRawArray()[(position + start) / Constants::Containers::dequeBlockSize][(position + start) % Constants::Containers::dequeBlockSize];
}

}

#endif // DEQUECORE_H_INCLUDED
